package com.leetcode.partition5;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @author `RKC`
 * @date 2021/10/6 10:38
 */
public class LC496下一个更大元素1 {

    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        return monotonicStack(nums1, nums2);
    }

    public static void main(String[] args) {
        int[] nums1 = {4, 1, 2}, nums2 = {1, 3, 4, 2};
        System.out.println(Arrays.toString(nextGreaterElement(nums1, nums2)));
    }

    private static int[] monotonicStack(int[] nums1, int[] nums2) {
        //记录nums1的信息 <nums[i], i>
        Map<Integer, Integer> nums1Table = new HashMap<>();
        int[] answers = new int[nums1.length];
        if (nums1.length == 0) return answers;
        Arrays.fill(answers, -1);
        for (int i = 0; i < nums1.length; i++) nums1Table.put(nums1[i], i);
        //nums2的单调栈，存放nums2元素的下标，如果当前元素比栈顶元素小，则直接入栈，否则当前元素就是栈顶元素的下一个更大元素
        Stack<Integer> s = new Stack<>();
        s.push(0);
        //遍历nums2的元素，只对在nums1中出现的进行处理
        for (int i = 1; i < nums2.length; i++) {
            if (nums2[s.peek()] < nums2[i]) {
                //从单调栈中弹出元素，直到为空或者栈顶比当前元素大的值，再将当前元素入栈
                while (!s.isEmpty() && nums2[s.peek()] < nums2[i]) {
                    //过滤元素，只有nums2的元素在nums1中出现过的才进行处理
                    if (nums1Table.containsKey(nums2[s.peek()])) {
                        answers[nums1Table.get(nums2[s.peek()])] = nums2[i];
                    }
                    s.pop();
                }
            }
            s.push(i);
        }
        return answers;
    }
}
